package work.lianbiao;

import work.Node;

import java.util.HashMap;
import java.util.Map;


public class Problem146 {


    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        //无参构造
        public DLinkedNode() {
        }

        //有参构造
        public DLinkedNode(int _key, int _value) {
            this.key = _key;
            this.value = _value;
        }
    }

    Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    //这里不知道为什么要加一个void ，利口上不用加
    public void LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode cacheNode = cache.get(key);
        if (cacheNode == null) {
            return -1;
        } else {
            MoveToHead(cacheNode);
            return cacheNode.value;
        }

    }

    private void MoveToHead(DLinkedNode cacheNode) {
        DeleteNode(cacheNode);
        AddToHead(cacheNode);
    }

    private void AddToHead(DLinkedNode cacheNode) {
        cacheNode.prev = head;
        head.next.prev = cacheNode;
        cacheNode.next = head.next;
        head.next = cacheNode;
    }

    private void DeleteNode(DLinkedNode cacheNode) {
        cacheNode.prev.next = cacheNode.next;
        cacheNode.next.prev = cacheNode.prev;
    }

    private DLinkedNode RemoveTail() {
        DLinkedNode res = tail.prev;
        DeleteNode(res);
        return res;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            AddToHead(newNode);
            size++;
            if (size > capacity) {
                DLinkedNode dLinkedNode = RemoveTail();
                size--;
                cache.remove(dLinkedNode);
            }
        } else {
            node.value = value;
            cache.put(key, node);
            MoveToHead(node);
        }
    }
}
